package com.zecan.floyd;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: lenovo
 * \* Date: 2021/10/19
 * \* Time: 10:07
 * \* Description:
 * \
 */
public class FloydAlgorithm {
    public static final int N = 65535;

    public static void main(String[] args) {
        char[] vertex = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = new int[][]{
                {0, 5, 7, N, N, N, 2}, {5, 0, N, 9, N, N, 3},
                {7, N, 0, N, 8, N, N}, {N, 9, N, 0, N, 4, N},
                {N, N, 8, N, 0, 5, 4}, {N, N, N, 4, 5, 0, 6},
                {2, 3, N, N, 4, 6, 0}};
        Graph graph = new Graph(vertex.length, vertex, matrix);
        graph.floyd();
        graph.show();
    }
}

class Graph {
    private char[] vertex; // 定义存放结点信息的数组
    private int[][] matrix; // 邻接矩阵
    private int[][] pre; // 定义存放前驱信息的数组

    public Graph(int length, char[] vertex, int[][] matrix) {
        pre = new int[length][length];
        this.vertex = vertex;
        this.matrix = matrix;
        // 初始化 前驱数组
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                pre[i][j] = i;
            }
        }
    }

    public void floyd() {
        int len = 0; // 记录中间的长度
        int i = 0,j = 0,k = 0;
        // 定义中间结点的循环
        for ( i = 0; i < vertex.length; i++) {
            //定义出发结点的循环
            for ( j = 0; j < vertex.length; j++) {
                // 定义终点结点的循环
                for ( k = 0; k < vertex.length; k++) {
                        len  = matrix[j][i] + matrix[i][k]; // 将 出发结点到中间结点 和 中间结点到终点的距离相加
                    if(len < matrix[j][k]) { // 如果 len 小于 出发结点直接到终点那么就将值赋给
                        matrix[j][k] = len;
                        pre[j][k] =  pre[i][k];
                    }
                }
            }
        }
    }
    public void show() {
        // 邻接矩阵
        for (int i = 0; i < vertex.length; i++) {
            for (int j = 0; j < vertex.length; j++) {
                System.out.print(vertex[i] + "->" +  vertex[j]+ " " + matrix[i][j] + " ");
            }
            System.out.println();
        }
        // 前驱结点
        for (int i = 0; i < vertex.length; i++) {
            for (int j = 0; j < vertex.length; j++) {
                System.out.print(vertex[pre[i][j]] + " ");
            }
            System.out.println();
        }
    }
}
